package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">删除二叉搜索树中的节点(Delete Node in a BST)</a>
 * <p>给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。</p>
 * <p>一般来说，删除节点可分为两个步骤：</p>
 * <ol>
 *     <li>首先找到需要删除的节点；</li>
 *     <li>如果找到了，删除它。</li>
 * </ol>
 * <p>
 * <b>示例：</b>
 * <pre><a href="https://leetcode.cn/problems/delete-node-in-a-bst/">查看示例</a></pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>节点数的范围 [0, 10^4].</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 *     <li>节点值唯一</li>
 *     <li>root 是合法的二叉搜索树</li>
 *     <li>-10^5 <= key <= 10^5</li>
 * </ul>
 * </p>
 * <b>进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。</b>
 *
 * @author c2b
 * @since 2023/5/22 15:48
 */
public class LC0450DeleteNode_M {

    static class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            //return deleteNodeByRecursion(root, key);
            return deleteNodeByIterator(root, key);
        }

        public TreeNode deleteNodeByIterator(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            // 1.如果删除的是根节点
            if (root.val == key) {
                // 如果根节点的左子节点为 null，返回右子树即可
                if (root.left == null) {
                    return root.right;
                }
                // 如果根节点的右子节点为 null，返回左子树即可
                if (root.right == null) {
                    return root.left;
                }
                // 将左子节点挂到右子树的最左子节点下面
                TreeNode temp = root.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                temp.left = root.left;
                return root.right;
            }
            // 2.如果删除的是非根节点
            // currNode:要删除的节点。currNodeParent：要删除节点的父节点
            TreeNode currNode = root;
            TreeNode currNodeParent = null;
            while (currNode != null && currNode.val != key) {
                currNodeParent = currNode;
                if (currNode.val < key) {
                    currNode = currNode.right;
                } else {
                    currNode = currNode.left;
                }
            }
            // 2.1 如果没找到要删除的节点
            if (currNode == null) {
                return root;
            }
            // 2.2 找到了要删除的节点
            // 2.2.1 要删除的节点没有子节点
            if (currNode.left == null && currNode.right == null) {
                if (currNodeParent.left == currNode) {
                    currNodeParent.left = null;
                } else {
                    currNodeParent.right = null;
                }
                return root;
            }
            // 2.2.2 要删除的节点没有左子节点
            else if (currNode.left == null) {
                // 其无左子：其右子顶替其位置，删除了该节点；
                if (currNode.val > currNodeParent.val) {
                    // 当前节点是否为父节点的右子节点？当前节点的右子树作为父节点的右子节点
                    currNodeParent.right = currNode.right;
                } else {
                    // 当前节点是否为父节点的左子节点？当前节点的左子树作为父节点的右子节点
                    currNodeParent.left = currNode.right;
                }
            }
            // 2.2.3 要删除的节点没有右子节点
            else if (currNode.right == null) {
                // 其无右子：其左子顶替其位置，删除了该节点；
                if (currNode.val > currNodeParent.val) {
                    // 当前节点是否为父节点的右子节点？当前节点的左子树作为父节点的右子节点
                    currNodeParent.right = currNode.left;
                } else {
                    // 当前节点是否为父节点的左子节点？当前节点的左子树作为父节点的左子节点
                    currNodeParent.left = currNode.left;
                }
            }
            // 2.2.4 删除的节点既有左子节点也有右子节点
            else {
                // 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
                TreeNode temp = currNode.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                temp.left = currNode.left;
                // 如果删除的节点是父节点的左子节点，那么以删除节点为根节点的树下所有节点仍为左子节点
                // 如果删除的节点是父节点的右子节点，那么以删除节点为根节点的树下所有节点仍为右子节点
                if (currNode.val > currNodeParent.val) {
                    // 当前节点是否为父节点的右子节点？当前节点的左子树作为父节点的左子节点
                    currNodeParent.right = currNode.right;
                } else {
                    // 当前节点是否为父节点的左子节点？当前节点的左子树作为父节点的左子节点
                    currNodeParent.left = currNode.right;
                }
            }
            return root;
        }

        public TreeNode deleteNodeByRecursion(TreeNode root, int key) {
            if (root == null) {
                return null;
            }
            if (root.val > key) {
                // 要删除的元素在左子树，返回删除完元素的左子树
                root.left = deleteNodeByRecursion(root.left, key);
            } else if (root.val < key) {
                // 要删除的元素在右子树，返回删除完元素的右子树
                root.right = deleteNodeByRecursion(root.right, key);
            } else {
                //root.val == key  删除的元素正好在节点上
                if (root.left == null) {
                    return root.right;
                }
                if (root.right == null) {
                    return root.left;
                }
                // 删的节点左不为空，右也不为空。
                // 找到右子树的最左子节点，将当前树的左子树挂在右子树的最左子节点下面。
                TreeNode temp = root.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                temp.left = root.left;
                return root.right;
            }
            return root;
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(7);
        Solution solution = new Solution();
        TreeNode newRoot = solution.deleteNode(root, 7);
        TreeNode.printTree(newRoot);
    }
}
